package tree;

import java.util.*;
import java.util.LinkedList;

public class LRUCache {
    private HashMap<Integer, Node> hashMap = new HashMap<>();//K:key V:Node
    private MyLinkedList linkedList;
    int capacity;

    public LRUCache(int capacity) {
        linkedList = new MyLinkedList();
        this.capacity = capacity;
    }


    public int get(int key) {
        Node n = hashMap.get(key);
        if (n != null) {
            int value = n.value;
            //update the position of the Node in linkedList
            linkedList.unlink(n);
            linkedList.addLast(n);
            return value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (hashMap.containsKey(key)) {
            //update the value of the Node
            Node n = hashMap.get(key);
            n.value = value;
            //update the position of the Node in linkedList
            linkedList.unlink(n);
            linkedList.addLast(n);
        } else {
            if (linkedList.size == capacity) {
                int delKey = linkedList.removeFirst();
                hashMap.remove(delKey);
                Node newNode = linkedList.addLast(key, value);
                hashMap.put(key, newNode);
            } else {
                Node newNode = linkedList.addLast(key, value);
                hashMap.put(key, newNode);
            }
        }
    }

    private class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value, Node prev, Node next) {
            this.key = key;
            this.value = value;
            this.prev = prev;
            this.next = next;
        }


    }

    private class MyLinkedList {
        Node first;
        Node last;
        int size;

        public MyLinkedList() {

        }

        public Node addLast(int key, int value) {
            Node newNode = new Node(key, value, last, null);
            Node l = last;
            last = newNode;
            if (l == null) {
                first = newNode;
            } else {
                l.next = newNode;
            }
            size++;
            return newNode;
        }

        public void addLast(Node newNode) {
            Node l = last;
            last = newNode;
            if (l == null) {
                first = newNode;
            } else {
                l.next = newNode;
                newNode.prev = l;
            }
            size++;
        }

        public int unlink(Node n) {
            Node prev = n.prev;
            Node next = n.next;
            if (prev == null) {
                //means n is first
                first = next;
            } else {
                prev.next = next;
            }
            if (next == null) {
                //means n is last
                last = prev;
            } else {
                next.prev = prev;
            }
            //make the now isolated
            n.prev = null;
            n.next = null;
            size--;
            return n.key;
        }

        public int removeFirst() {
            if (first == null) {
                throw new NoSuchElementException();
            }
            return unlink(first);
        }
    }


    public static void main(String[] args) {
        LRUCache cache = new LRUCache(10);
//
        cache.put(10, 13);
        cache.put(3, 17);
//        System.out.println(cache.get(1));       // 返回  1
        cache.put(6, 11);
        cache.put(10, 5);
        cache.put(9, 10);
        cache.put(2, 19);
        cache.get(2);
        cache.get(3);
        cache.put(5, 25);
        cache.put(9, 22);
        cache.put(5, 5);
        cache.put(1, 30);
        cache.put(9, 12);
        cache.get(5);
        cache.get(9);
        cache.put(4, 30);
        cache.put(9, 3);
        cache.get(9);
        cache.get(10);
        cache.get(10);
        cache.put(6, 14);
        cache.put(3, 1);
        cache.get(3);
        cache.put(10, 11);
        cache.put(2, 14);
        cache.get(1);
        cache.get(5);
        cache.get(4);
        cache.put(11, 4);
        cache.put(12, 24);
        cache.put(5, 18);
        cache.put(7, 23);
        cache.get(12);
        cache.put(3, 27);
        cache.put(2, 12);
        cache.get(5);
        cache.put(2, 9);
        cache.put(13, 4);
        cache.put(8, 18);
        cache.put(1, 7);
        System.out.println(cache.get(6));

//        System.out.println(cache.get(1));       // 返回 -1 (未找到)
//        System.out.println(cache.get(2));       // 返回  3
//        System.out.println(cache.get(4));       // 返回  4
    }
}
